//
// Created by fengg on 2020/5/5.
//

///
/// Hw_7_1_Ver_1 复用了 Hw_3_1_ver_2 的诸多代码.
/// 最后的表达式计算也采用了 Hw_3_1_ver_2 的 eval 函数
///


/// 2020/5/17 16:52 说明
/// 建议阅读顺序:  main 函数 -> CreateChain 函数 -> BuildTreeFromChain 函数
///
/// 这里的求值我直接用了实验3(?)的后缀表达式求值.主要就是eval这个函数,其他函数
/// 都是辅助性质的,以及下面的宏定义都是我个人的习惯,可以忽略把(?)
/// 大部分都是注释性文字

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define None  0
#define __OUT__
#define __IN__
#define _DOUBLE(x)     *(double  *)(x)
#define _ADDR(x)     ((x)->stack+(x)->item_size*(x)->top)
const char  sp[]             = " "                                                  ;
const char  op_ack[]         = {'+','-','*','/','^','\0'}                           ;
const int   op_level[]       = { 0,  0,  1,  1,  2 }                                ;
const char  NULL_CHAR        = '\0'                                                 ;


typedef struct {
    void *stack;
    int top;
    size_t item_size;
    int max_size;
} Stack ;

typedef struct _bin_tree {
    union {
        char op;
        double opd;
    } data ;
    unsigned int type;
    struct _bin_tree  *parent;
    struct _bin_tree  *l_child;
    struct _bin_tree  *r_child;
} BinTree ;

typedef struct _chain {
    BinTree         *tree;
    struct _chain   *next,
                    *previous,
                    *next_op;
} Chain ;

enum _data_type {
    operator            =    0,
    operand             =    1,
    spec                =    3,
};
enum OP_MODE {
    R_Parentheses_Mode  =   -1,
    L_Parentheses_Mode  =   -2,
    Number_Mode         =    1,
    Operator_Mode       =    2,
    Single_Mode         =    5
};

int init(Stack *s,size_t item_size,size_t num){
    s->top = -1;
    s->stack = malloc(item_size*num);
    s->item_size = item_size;
    s->max_size = num;
    return 0;
}

int isEmpty(Stack *s){
    return s->top < 0;
}

int isFill(Stack *s){
    return s->top >= s->max_size-1;
}

int push(Stack *s,const void *v,size_t t){
    if(!isFill(s)){
        ++s->top;
        memcpy(_ADDR(s),v,t);
        return 1;
    }
    return 0;
}

void* pop(Stack *s){
    if(!isEmpty(s)){
        void *p = _ADDR(s);
        --s->top;
        return p;
    }

    return NULL;
}

/// 运算函数
/// \param v1
/// \param v2
/// \param optor
/// \return
double op(double v1,double v2,char optor){
    double res = 0;
    switch (optor){
        case '+':
            res = v1+v2;
            break;
        case '-':
            res = v1-v2;
            break;
        case '*':
            res = v1*v2;
            break;
        case '/':
            res = v1/v2;
            if(!v2){
                puts("error");
                exit(0);
            }
            break;

        default:
            break;
    }
    return res;
}

/// 操作符优先级对比.详情见Hw_3_1_ver_2
/// \param op1
/// \param op2
/// \return
int op_cmp(char op1, char op2) {
    int c1,c2;
    for (c1 = 0;op1 != op_ack[c1] && op_ack[c1] != NULL_CHAR; ++c1);
    for (c2 = 0;op2 != op_ack[c2] && op_ack[c2] != NULL_CHAR; ++c2);
    return op_level[c1] - op_level[c2];
}
const static char OP_FORMAT[]  =    "%c ";
const static char OPD_FORMAT[] =    "%g ";
/// 控制台输出
/// \param binTree
void print_tree(BinTree *binTree){
    switch (binTree->type){
        case 3:
        case 0:
            printf(OP_FORMAT,binTree->data.op);
            break;
        case 1:
            printf(OPD_FORMAT,binTree->data.opd);
            break;
    }
}
/// 输出到字符串c
/// \param binTree
/// \param c

void sprint_tree(BinTree *binTree,char *c){
    char temp[16] = {None};
    switch (binTree->type){
        case spec:
        case operator:
            sprintf(temp,OP_FORMAT,binTree->data.op);
            break;
        case operand:
            sprintf(temp,OPD_FORMAT,binTree->data.opd);
            break;
    }
    strncat(c,temp,16);
}

/// 命名很奇怪,我不管哈哈哈
/// \param binTree 树

void GoM(BinTree *binTree) {
    if(!binTree)
        return;
    GoM(binTree->l_child);
    print_tree(binTree);
    GoM(binTree->r_child);
}
void GoF(BinTree *binTree) {
    if(!binTree)
        return;
    print_tree(binTree);
    GoF(binTree->l_child);
    GoF(binTree->r_child);
}
void GoB(BinTree *binTree,char **c) {
    if(!binTree)
        return;
    if(!(*c)){
        *c = malloc(256);
        memset(*c,None,256);
    }
    GoB(binTree->l_child,c);
    GoB(binTree->r_child,c);
    sprint_tree(binTree,*c);
}

/// 最最最主要的逻辑实现函数.
/// 从树链转换为树
/// \param pTree    [OUT]
/// \param pChain   [IN]

void BuildTreeFromChain(
         __OUT__   BinTree  **pTree,
         __IN__    Chain  *pChain) {
    BinTree *root = NULL;
    Chain *pCurr;
    Chain *p;
    for (p=pChain->next; p !=NULL ; p =p->next) {
        switch (p->tree->type){
            /// spec 只是将操作符当成操作数操作.这是为了递归,和单目运算考虑的
            /// 单目 如'-' 和括号里头的内容 (...) 会被提前生成树,并设定其root结点为 spec 类型
            case spec:
            case operand:
                if( !p->previous->tree ){
                    p->next->tree->l_child = p->tree;
                    if(!root) root = p->next->tree;
                } else if (p->next){
                    if( op_cmp(p->previous->tree->data.op,p->next->tree->data.op) >= 0){
                        p->previous->tree->r_child = p->tree;
                        p->tree->parent = p->previous->tree;
                    } else{
                        p->next->tree->l_child = p->tree;
                        p->tree->parent = p->next->tree;
                    }
                } else {
                    p->previous->tree->r_child = p->tree;
                    p->tree->parent = p->previous->tree;
                }
                break;
            case operator:
                pCurr = p;
                /// 如果不是最后一个而且本身优先级小于pCurr操作符,pCurr移动至下一个
                while(pCurr->next_op && op_cmp(p->tree->data.op,pCurr->next_op->tree->data.op) < 0){
                    pCurr = pCurr->next_op;
                }
                /// 判断是否是最后一个
                if(pCurr->next_op){
                    /// 是否已经被加入,即是否有父节点
                    if(!pCurr->tree->parent){
                        pCurr->next_op->tree->l_child = p->tree;
                        p->tree->parent = pCurr->next_op->tree;
                    }
                    if(root == p->tree) root = pCurr->next_op->tree;
                    if(pCurr != p){
                        p->tree->r_child = pCurr->tree;
                        pCurr->tree->parent =  p->tree;
                    }
                }
                else {
                    if(pCurr != p)
                        p->tree->r_child = pCurr->tree;
                }
        }
    }
    *pTree = root;
}

///
/// 将字符串 data 转换为树链,用做下一步 BuildTreeFromChain 处理
/// \param pChain   转换后的Chain  [OUT]
/// \param data     需转换的字符串  [IN]

void CreateChain(
        __OUT__  Chain  **pChain,
        __IN__   char    *data) {
    Chain *temp,*curr,*last_op = NULL;
    char *curr_pos = data;
    if(!(*pChain))
        *pChain = (Chain *) malloc(sizeof(Chain));
    memset(*pChain,None, sizeof(Chain));
    curr  = *pChain;
    while (*curr_pos){
        BinTree *tree = malloc(sizeof(BinTree));
        temp = (Chain *) malloc(sizeof(Chain));
        memset(tree,None, sizeof(BinTree));
        memset(temp,None, sizeof(Chain));
        if(!isdigit(*curr_pos)){
            if(*curr_pos == '-'){
                if(curr_pos-1 < data || (!isdigit(*(curr_pos-1)) && *(curr_pos-1) != ')')){
                    BinTree *pT = malloc(sizeof(BinTree));
                    BinTree *pR = malloc(sizeof(BinTree));
                    BinTree *pL = malloc(sizeof(BinTree));
                    memset(pT,None, sizeof(BinTree));
                    memset(pR,None, sizeof(BinTree));
                    memset(pL,None, sizeof(BinTree));
                    pT->type = spec;
                    pT->data.op = '-';
                    pT->r_child = pR;
                    pT->l_child = pL;
                    pR->type = operand;
                    pL->type = operand;
                    pR->data.opd = strtod(curr_pos+1,&curr_pos);
                    pL->data.opd = 0;
                    temp->tree = pT;
                    curr->next = temp;
                    temp->previous = curr;
                    curr = curr->next;
                    continue;
                }
            } else if (*curr_pos == '('){
                /// 我对这些写死的数字很不安心....但目前拿它们没办法
                /// TODO
                char inter_data[128] = {None};
                char* star = ++curr_pos;
                size_t  i,match;
                Chain *chain = NULL;
                BinTree *inter_tree = NULL;
                for (i = 0,match = 1; match != 0; ++i){
                    if(curr_pos[i] == '('){
                        ++match;
                    } else if (curr_pos[i] == ')'){
                        --match;
                    }
                }
                memcpy(inter_data,star,i-1);
                CreateChain(&chain,inter_data);
                BuildTreeFromChain(&inter_tree,chain);
                temp->tree = inter_tree;
                inter_tree->type = spec;
                curr->next = temp;
                temp->previous = curr;
                curr = curr->next;
                curr_pos += i;
                continue;
            }
            tree->data.op = *curr_pos;
            tree->type = operator;
            ++curr_pos;
        } else {
            tree->data.opd = strtod(curr_pos,&curr_pos);
            tree->type = 1;
        }

        temp->tree = tree;
        curr->next = temp;
        temp->previous = curr;
        if(!tree->type){
            if(!last_op){
                last_op = temp;
            } else {
                last_op->next_op = temp;
                last_op = temp;
            }
        }
        curr = curr->next;
    }
}

size_t get_rpn_token(const char *rpn,char **token){
    size_t i=1;
    if(rpn[0] == NULL_CHAR || rpn[0] == '\n')
        return 0;
    while (rpn[i] != NULL_CHAR && rpn[i] != sp[0])
        ++i;
    *token = calloc(i+1,1);
    memcpy(*token,rpn,i);
    return i;
}



int get_mode(char *s,int *mode){
    if(isdigit(s[0]) || isalpha(s[0]))
        *mode = Number_Mode;  // number_mode
    else if (s[0] == '(')
        *mode = L_Parentheses_Mode;
    else if (s[0] == ')')
        *mode = R_Parentheses_Mode;
    else if (!strcmp("$-",s))   //single op mode
        *mode = Single_Mode;

    else
        *mode = Operator_Mode; // op_mode
    return 0;
}

/// 后缀表达式求值
/// 略
/// \param rpn_str
/// \return
double eval(char *rpn_str){
    size_t rpn_offset = 0,token_len=0;
    Stack *Number_stack;
    char *token;
    double number,res,mid_res=0;
    int mode;
    Number_stack = (Stack *) malloc(sizeof(Stack));
    init(Number_stack, sizeof(double),50);
    while ((token_len = get_rpn_token(&rpn_str[rpn_offset],&token))!= 0 ){
        rpn_offset += token_len+1;
        get_mode(token,&mode);
        switch (mode){
            case Number_Mode:

                number = strtod(token,NULL);
                push(Number_stack,&number, sizeof(double));
                break;
            case Operator_Mode:
                mid_res=op(
                        _DOUBLE(pop(Number_stack)),
                        _DOUBLE(pop(Number_stack)),
                        token[0]

                );
                push(Number_stack,&mid_res, sizeof(double));
                break;
            default:
                printf("Invalid Mode\nThe Token Is %s",token);
        }

    }
    res = _DOUBLE(pop(Number_stack));
    free(Number_stack->stack);
    free(Number_stack);
    free(token);
    return res;
}

void ChainGc(Chain *pChain){
    Chain *pNext,*pCurr = pChain;
    while (pCurr){
        pNext = pCurr->next;
        free(pCurr->tree);
        free(pCurr);
        pCurr = pNext;
    }
}

int main(){

    char raw_data[256] = {None};
    double res = 0;
    char *RPN = NULL;
    Chain *chain = NULL;
    BinTree *tree = NULL;
    //表达式输入
    scanf("%[^\n]",raw_data);
    //表达式 转换成 链表 , 链的元素是树的结点
    CreateChain(&chain,raw_data);
    //由链生成二叉树
    BuildTreeFromChain(&tree,chain);
    GoF(tree); putchar('\n');
    GoM(tree); putchar('\n');
    GoB(tree,&RPN);
    puts(RPN);
    res = eval(RPN);
    printf("%.3f\n",res);

    free(RPN);
    ChainGc(chain);
    return 0;
}
